{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Value to Get Positive Step by Step Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minStartValue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #逐步求和得到正数的最小值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code>&nbsp;。你可以选定任意的&nbsp;<strong>正数</strong> startValue 作为初始值。</p>\n",
    "\n",
    "<p>你需要从左到右遍历 <code>nums</code>&nbsp;数组，并将 startValue 依次累加上&nbsp;<code>nums</code>&nbsp;数组中的值。</p>\n",
    "\n",
    "<p>请你在确保累加和始终大于等于 1 的前提下，选出一个最小的&nbsp;<strong>正数</strong>&nbsp;作为 startValue 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [-3,2,-3,4,2]\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>如果你选择 startValue = 4，在第三次累加时，和小于 1 。\n",
    "<strong>                累加求和\n",
    "&nbsp;               startValue = 4 | startValue = 5 | nums\n",
    "</strong>&nbsp;                 (4 <strong>-3</strong> ) = 1  | (5 <strong>-3</strong> ) = 2    |  -3\n",
    "&nbsp;                 (1 <strong>+2</strong> ) = 3  | (2 <strong>+2</strong> ) = 4    |   2\n",
    "&nbsp;                 (3 <strong>-3</strong> ) = 0  | (4 <strong>-3</strong> ) = 1    |  -3\n",
    "&nbsp;                 (0 <strong>+4</strong> ) = 4  | (1 <strong>+4</strong> ) = 5    |   4\n",
    "&nbsp;                 (4 <strong>+2</strong> ) = 6  | (5 <strong>+2</strong> ) = 7    |   2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>最小的 startValue 需要是正数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,-2,-3]\n",
    "<strong>输出：</strong>5\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 100</code></li>\n",
    "\t<li><code>-100 &lt;= nums[i] &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-value-to-get-positive-step-by-step-sum](https://leetcode.cn/problems/minimum-value-to-get-positive-step-by-step-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-value-to-get-positive-step-by-step-sum](https://leetcode.cn/problems/minimum-value-to-get-positive-step-by-step-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[-3,2,-3,4,2]', '[1,2]', '[1,-2,-3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        cum_sum=[]\n",
    "        cum_sum.append(nums[0])\n",
    "        for i in range(1,len(nums)):\n",
    "            cum_sum.append(cum_sum[i-1]+nums[i])\n",
    "        \n",
    "        return max(1, 1-min(cum_sum))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        x = 1 \n",
    "        y = 1\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] + x < 1:\n",
    "                y = y + (1 - (nums[i] + x))\n",
    "                x = 1\n",
    "                continue\n",
    "            else:\n",
    "                x =  nums[i] + x\n",
    "        return y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        x = 0\n",
    "        mx = 1e10\n",
    "        for i in nums:\n",
    "            x += i\n",
    "            mx = min(mx, x)\n",
    "        return max(1,1-mx)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        res=arr=0\n",
    "        for num in nums:\n",
    "            res+=num\n",
    "            arr = min(arr,res)\n",
    "        return 1-arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        from itertools import accumulate\n",
    "        return max(1,1-min(list(accumulate(nums))))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        f=[x for x in nums if x<0]\n",
    "        for i in range(1,-sum(f)+2):\n",
    "            flag=True\n",
    "            sumn=i\n",
    "            for j in nums:\n",
    "                sumn+=j\n",
    "                if sumn<1:\n",
    "                    flag=False\n",
    "            if flag :\n",
    "                return i            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        startValue = 1  # 初始化startValue为1\n",
    "        currentSum = startValue  # 当前累加和\n",
    "\n",
    "        for num in nums:\n",
    "            currentSum += num\n",
    "            if currentSum < 1:\n",
    "                startValue += 1 - currentSum  # 调整startValue使得累加和大于等于1\n",
    "                currentSum = 1\n",
    "\n",
    "        return startValue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        accSum,accSumMin = 0,0\n",
    "        for num in nums:\n",
    "            accSum += num\n",
    "            accSumMin = min(accSumMin,accSum)\n",
    "        return -accSumMin+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        dp = [0]*len(nums)\n",
    "        dp[0] = nums[0]\n",
    "        for i in range(len(nums)-1):\n",
    "            dp[i+1] = dp[i] +nums[i+1]\n",
    "        return 1-min(dp) if min(dp) < 1 else 1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        accSum, accSumMin = 0, 0\n",
    "        for num in nums:\n",
    "            accSum += num\n",
    "            accSumMin = min(accSumMin, accSum)\n",
    "        return -accSumMin + 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        n=1\n",
    "        s=1\n",
    "        x=[]\n",
    "        while x==[]:\n",
    "            y=[]\n",
    "            s=n\n",
    "            for i in nums:\n",
    "                s+=i\n",
    "                y.append(s)\n",
    "            if all([s>=1 for s in y]):\n",
    "                x.append(n)\n",
    "            else:\n",
    "                n+=1\n",
    "        return x[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        min_value = 1\n",
    "        start_value = 1\n",
    "        for i in range(len(nums)):\n",
    "            start_value += nums[i]\n",
    "            min_value = min(min_value, start_value)\n",
    "        if min_value < 1:\n",
    "            return 2 - min_value\n",
    "        else:\n",
    "            return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        # sums = [0]\n",
    "        # n = len(nums)\n",
    "        # for i in range(n):\n",
    "        #     sums.append(sums[-1] + nums[i])\n",
    "        # min_sums = min(sums)\n",
    "        # return 1-min_sums if min_sums < 0 else 1\n",
    "\n",
    "        n = len(nums)\n",
    "        def f(mid):\n",
    "            for i in range(n):\n",
    "                mid += nums[i]\n",
    "                if mid <1:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        # return bisect_left(range(1, -min(nums) * n +  1), True, key=f) + 1\n",
    "        l, r = 0, -min(nums) * n +  1\n",
    "        while l + 1 < r:\n",
    "            mid = (r+l) // 2\n",
    "            if f(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid\n",
    "        return max(r, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        mn =0\n",
    "        tem =0\n",
    "        for i in nums:\n",
    "            tem += i\n",
    "            mn = min([mn,tem])\n",
    "        return 1-mn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        m, s = 0, 0\n",
    "        for n in nums:\n",
    "            s += n\n",
    "            m = min(m, s)\n",
    "        return -m + 1 if m < 0 else 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        n,tmp = 0,inf\n",
    "        for i in nums:\n",
    "            n += i\n",
    "            tmp = min(n,tmp)\n",
    "        return max(1-tmp,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        x = 0\n",
    "        mx = 1e10\n",
    "        for i in nums:\n",
    "            x += i\n",
    "            mx = min(mx, x)\n",
    "        print(mx)\n",
    "        return max(1,1-mx)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        ans = 1\n",
    "        acc = 0 # 前缀和\n",
    "        for x in nums:\n",
    "            acc += x\n",
    "            if acc < 0:\n",
    "                ans = max(ans, 1 - acc)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        a,b,c=1,0,1\n",
    "        while b<len(nums):\n",
    "            a+=nums[b]\n",
    "            if a<1:\n",
    "                c+=1\n",
    "                a=c\n",
    "                b=0\n",
    "            else:\n",
    "                b+=1\n",
    "        return c\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        l,r = 1,10 ** 4 + 5\n",
    "        while l <= r:\n",
    "            mid = l + (r - l) // 2\n",
    "            flag = 1\n",
    "            cur = mid\n",
    "            for c in nums:\n",
    "                cur += c\n",
    "                if cur < 1:\n",
    "                    flag = 0\n",
    "                    break\n",
    "            if flag:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return r + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        temp=0\n",
    "        ans=0\n",
    "        for i in nums:\n",
    "            temp+=i\n",
    "            if temp<0:\n",
    "                ans=max(ans,-temp+1)\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        return 1 if ans==0 else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        psum=0\n",
    "        minval=0\n",
    "        for i in range(len(nums)):\n",
    "            psum+=nums[i]\n",
    "            minval=min(minval,psum)\n",
    "        return 1-minval\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        return max(1, 1 - min(accumulate(nums)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        sum_nums = 0\n",
    "        min_nums = 0\n",
    "        for i in nums:\n",
    "            sum_nums += i\n",
    "            min_nums = min(min_nums,sum_nums)\n",
    "        return 1-min_nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        start = 0\n",
    "        he = []\n",
    "        for i in range(len(nums)):\n",
    "            start = start+nums[i]\n",
    "            he.append(start)\n",
    "        minnum = min(he)\n",
    "        i = 1\n",
    "        while True:\n",
    "            if i+minnum>=1:\n",
    "                return i\n",
    "            i = i+1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        list1 = list(itertools.accumulate(nums))\n",
    "        if min(list1) <=0:\n",
    "            sv = abs(min(list1))+1\n",
    "        else:\n",
    "            sv = 1\n",
    "        return sv"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        accSum, accSumMin = 0, 0\n",
    "        for num in nums:\n",
    "            accSum += num\n",
    "            accSumMin = min(accSumMin, accSum)\n",
    "        return -accSumMin + 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        return max(1, 1 - min(accumulate(nums)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        accSum, accSumMin = 0, 0\n",
    "        for num in nums:\n",
    "            accSum += num\n",
    "            accSumMin = min(accSumMin, accSum)\n",
    "        return -accSumMin + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        m, s = 0, 0\n",
    "        for n in nums:\n",
    "            s += n\n",
    "            m = min(m, s)\n",
    "        return -m + 1 if m < 0 else 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        m = 0\n",
    "        s = 0\n",
    "        for i in nums:\n",
    "            s += i\n",
    "            if s < m:\n",
    "                m = s\n",
    "        return -m + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        count = 0\n",
    "        mincount = nums[0]\n",
    "        for num in nums:\n",
    "            count += num\n",
    "            if count < mincount:\n",
    "                mincount = count\n",
    "        if mincount >= 1:\n",
    "            return 1 \n",
    "        else:\n",
    "            return 1 - mincount "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        _min=0\n",
    "        c=0\n",
    "        for n in nums:\n",
    "            c+=n\n",
    "            if c<_min:\n",
    "                _min=c\n",
    "        if _min==0:\n",
    "            return 1\n",
    "        return -_min+1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        sun = [0]\n",
    "        sum0=0\n",
    "        for i in nums :\n",
    "            sum0 += i\n",
    "            sun.append(sum0)\n",
    "        return abs(min(sun))+1\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        cur = 0\n",
    "        min_res = 0\n",
    "        for num in nums:\n",
    "            cur += num\n",
    "            if cur < min_res:\n",
    "                min_res = cur\n",
    "        return (1 - min_res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        return max(1, 1 - min(accumulate(nums)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        ret = 1\n",
    "        s = inf\n",
    "        temp = 0\n",
    "        for x in nums:\n",
    "            temp += x\n",
    "            s = min(temp, s)\n",
    "        return 1 - s if s < 1 else 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        startValue = max([1, 1 - nums[0]])\n",
    "        gameOver = False\n",
    "        while not gameOver:\n",
    "            temp = copy.deepcopy(startValue)\n",
    "            for i in range(len(nums)):\n",
    "                temp += nums[i]\n",
    "                if temp < 1:\n",
    "                    break\n",
    "                if i == len(nums) - 1:\n",
    "                    gameOver = True\n",
    "                    break\n",
    "            startValue += 1\n",
    "        return startValue - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        k=0\n",
    "        v=0\n",
    "        for  i in nums:\n",
    "            k+=i\n",
    "            if k<v:\n",
    "                v=k\n",
    "        return abs(v)+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        nums_add_gradual = [sum(nums[:i+1])for i in range(len(nums))]\n",
    "        min_value = min(nums_add_gradual)\n",
    "        if min_value >= 1:\n",
    "            return 1\n",
    "        else:\n",
    "            return abs(min_value)+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        if nums[0]>=0:\n",
    "            startValue = 1\n",
    "        else:\n",
    "            startValue = 1-nums[0]\n",
    "        res = startValue\n",
    "        startValue = startValue+nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            if startValue+nums[i]<1:\n",
    "\n",
    "                res = res+ (1-startValue-nums[i])\n",
    "                startValue = 1\n",
    "            else:\n",
    "                startValue += nums[i]\n",
    "            print([startValue,res])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        res = float('inf')\n",
    "        cur=0\n",
    "        for i in nums:\n",
    "            cur +=i\n",
    "            res=min(cur,res)\n",
    "\n",
    "        return max(1,1-res)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        accSum, accSumMin = 0, 0\n",
    "        for num in nums:\n",
    "            accSum += num\n",
    "            accSumMin = min(accSumMin, accSum)\n",
    "        return -accSumMin + 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        ans = s = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            s += x\n",
    "            nums[i] = s\n",
    "        m = min(nums)\n",
    "        return 1 - m if m < 1 else 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        s = 0\n",
    "        temp = 0\n",
    "        for x in nums:\n",
    "            temp += x\n",
    "            s = min(temp, s)\n",
    "        return 1 - s\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        accSum, accSumMin = 0, 0\n",
    "        for num in nums:\n",
    "            accSum += num\n",
    "            accSumMin = min(accSumMin, accSum)\n",
    "        return -accSumMin + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pos = 1\n",
    "        total = 1\n",
    "        for i in range(n):\n",
    "            total += nums[i]\n",
    "            if total < 1:\n",
    "                pos += 1 - total\n",
    "                total += 1 - total\n",
    "        return pos"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        pre_sum=0\n",
    "        ans=0\n",
    "        for num in nums:\n",
    "            pre_sum+=num\n",
    "            ans=min(ans, pre_sum)\n",
    "        return 1-ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        count = 0\n",
    "        mincount = nums[0]\n",
    "        for num in nums:\n",
    "            count += num\n",
    "            if count < mincount:\n",
    "                mincount = count\n",
    "        if mincount >= 1:\n",
    "            return 1 \n",
    "        else:\n",
    "            return 1 - mincount "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        starValue = 0\n",
    "        min1 = 0\n",
    "        for i in nums:\n",
    "            starValue += i\n",
    "            min1 = min(starValue ,min1)\n",
    "        return -min1 + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        startValue = 0\n",
    "        sum = 0\n",
    "        for i in range(len(nums)):\n",
    "            sum += nums[i]\n",
    "            if sum <= 0:\n",
    "                startValue = max(startValue,1-sum)\n",
    "            else:\n",
    "                startValue = max(startValue,1)\n",
    "        return startValue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        tmp = 0\n",
    "        res = 1\n",
    "        for n in nums:\n",
    "            tmp = tmp + n\n",
    "            m = 1 - tmp\n",
    "            if m>res:res=m\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        list1=[0]*n\n",
    "        for i in range(n):\n",
    "            list1[i]=sum(nums[:i+1])\n",
    "        res=1\n",
    "        for i in list1:\n",
    "            res=max(res,1-i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        s = 0\n",
    "        max_num = 0\n",
    "        for i in nums:\n",
    "            s += i\n",
    "            max_num = max(max_num, -s)\n",
    "        return max_num + 1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        ans,tot=1,0\n",
    "        for x in nums:\n",
    "            tot+=x\n",
    "            if tot<=0:\n",
    "                ans=max(ans,1-tot)\n",
    "        return ans\n",
    "\n",
    "            \n",
    "        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        a=0\n",
    "        c=0\n",
    "        for b in nums:\n",
    "            a+=b\n",
    "            c=min(c,a)\n",
    "        return 1-c\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        sum_nums = min_sum = 0\n",
    "        for num in nums:\n",
    "            sum_nums += num\n",
    "            min_sum = min(min_sum, sum_nums)\n",
    "        return 1 - min_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        a=0\n",
    "        b=1\n",
    "        for i in nums:\n",
    "            a+=i\n",
    "            b=max(b,1-a)\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        l = len(nums)\n",
    "        now = nums[0]\n",
    "        minvalue = now\n",
    "        for i in range(1, l):\n",
    "            now += nums[i] \n",
    "            if now < minvalue:\n",
    "                minvalue = now\n",
    "        if minvalue < 0:\n",
    "            return -minvalue + 1\n",
    "        else:\n",
    "            return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        minimizem = nums[0]\n",
    "        cache = 0\n",
    "        for i in nums:\n",
    "            cache += i\n",
    "            if cache < minimizem:\n",
    "                minimizem = cache\n",
    "        return 1 if minimizem >= 0 else 1-minimizem\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:return max(-min(accumulate(nums)), 0) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        ans=nums[0]\n",
    "        for i in range(1, n):\n",
    "            nums[i]=nums[i]+nums[i-1]\n",
    "            ans=min(ans, nums[i])\n",
    "        ans=1-ans\n",
    "        return ans if ans >1 else 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        f=[x for x in nums if x<0]\n",
    "        for i in range(1,-sum(f)+2):\n",
    "            flag=True\n",
    "            sumn=i\n",
    "            for j in nums:\n",
    "                sumn+=j\n",
    "                if sumn<1:\n",
    "                    flag=False\n",
    "            if flag and f:\n",
    "                return i\n",
    "            elif flag:\n",
    "                return 1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        result = 1\n",
    "        currSum = 1\n",
    "        for i in nums:\n",
    "            if (tmp := currSum + i) <= 0:\n",
    "                result -= tmp -1\n",
    "                currSum = 1\n",
    "            else:\n",
    "                currSum += i\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        sn = [0]*(n+1)\n",
    "        min = 0\n",
    "        for i in range(1,n+1):\n",
    "            sn[i] = sn[i-1]+nums[i-1]\n",
    "            if sn[i]<min:\n",
    "                min = sn[i]\n",
    "        for i in range(10000):\n",
    "            if i + min >= 1:\n",
    "               return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        accSum, accSumMin = 0, 0\n",
    "        for num in nums:\n",
    "            accSum += num\n",
    "            accSumMin = min(accSumMin, accSum)\n",
    "        return -accSumMin + 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        # presum:\n",
    "        presum = [nums[0]]\n",
    "        for v in nums[1:]:\n",
    "            presum.append(presum[-1] + v)\n",
    "        if min(presum) >= 0:\n",
    "            return 1\n",
    "        else:\n",
    "            return 1 - min(presum)\n",
    "\n",
    "\n",
    "        # solution 1:\n",
    "        # res = 1\n",
    "        # start = res\n",
    "        # while True: \n",
    "        #     tmp = start\n",
    "        #     record = []\n",
    "        #     for v in nums:\n",
    "        #         tmp += v\n",
    "        #         record.append(tmp)\n",
    "        #     if min(record) > 0:\n",
    "        #         return start\n",
    "        #     start += 1\n",
    "        # return start\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        ans = s = 1\n",
    "        for x in nums:\n",
    "            s += x\n",
    "            if s <= 0:\n",
    "                ans += 1 - s\n",
    "                s += 1 - s\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        accSum, accSumMin = 0, 0\n",
    "        for num in nums:\n",
    "            accSum += num\n",
    "            accSumMin = min(accSumMin, accSum)\n",
    "        return -accSumMin + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        newSum = nums[0]\n",
    "        minSum = nums[0]\n",
    "        for n in nums[1:]:\n",
    "            newSum += n\n",
    "            if newSum < minSum:\n",
    "                minSum = newSum\n",
    "        return max(1, 1 - minSum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        ans = 1\n",
    "        s = 0\n",
    "        for num in nums:\n",
    "            s += num\n",
    "            if s <= 0:\n",
    "                ans = max(ans, -s+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        minn = nums[0]\n",
    "        s = 0\n",
    "        for v in nums:\n",
    "            s += v \n",
    "            minn = min(minn, s)\n",
    "        \n",
    "        return 1 if minn > 0 else -minn + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        res = min(accumulate(nums))\n",
    "        return 1 if res >= 0 else -res + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        # 初始化最小前缀和为 0 和当前前缀和为 0\n",
    "        min_sum = 0\n",
    "        current_sum = 0\n",
    "        \n",
    "        # 遍历数组，计算前缀和，并更新最小前缀和\n",
    "        for num in nums:\n",
    "            current_sum += num\n",
    "            min_sum = min(min_sum, current_sum)\n",
    "        \n",
    "        # 计算并返回最小的 startValue，确保累加和始终大于等于 1\n",
    "        return 1 - min_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        l = len(nums)\n",
    "        now = nums[0]\n",
    "        minvalue = now\n",
    "        for i in range(1, l):\n",
    "            now += nums[i] \n",
    "            if now < minvalue:\n",
    "                minvalue = now\n",
    "        if minvalue < 0:\n",
    "            return -minvalue + 1\n",
    "        else:\n",
    "            return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        min_sum = sys.maxsize\n",
    "        num_sum = 0\n",
    "        for i in nums:\n",
    "            num_sum += i\n",
    "            if num_sum < min_sum:\n",
    "                min_sum = num_sum\n",
    "        if min_sum >= 0:\n",
    "            return 1\n",
    "        else:\n",
    "            return -min_sum + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        ans = s = -2\n",
    "        for x in nums:\n",
    "            s += x\n",
    "            ans = min(ans, s)\n",
    "        return ~ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        pre_sum = nums\n",
    "        for i in range(len(nums)):\n",
    "            if i == 0:\n",
    "                pre_sum[i] = nums[i]\n",
    "            else:\n",
    "                pre_sum[i] = pre_sum[i - 1] + nums[i]\n",
    "        return abs(min(pre_sum)) + 1 if min(pre_sum) < 0 else 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minStartValue(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        start=inf\n",
    "        for i in nums:\n",
    "            ans+=i\n",
    "            start=min(ans,start)\n",
    "        return abs(start)+1 if start<0 else 1\n",
    "\n",
    "            \n",
    "        \n",
    "            \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
